// https://www.lintcode.com/problem/palindrome-linked-list/my-submissions

/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param head: A ListNode.
     * @return: A boolean.
     */
    bool isPalindrome(ListNode * head) {
        // 错的，注意这样原链表已经翻转了
        // ListNode * p = NULL;
        // ListNode * cur = head;
        // while (cur)
        // {
        //     ListNode * tmp = cur->next;
        //     cur->next = p;
        //     p = cur;
        //     cur = tmp;
        // }
        // while (p && head)
        // {
        //     if (p->val != head->val) return false;
        //     p = p->next;
        //     head = head->next;
        // }
        // return true;
        ListNode * fast = head;
        ListNode * slow = head;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode * p = NULL;
        while (slow)
        {
            ListNode * tmp = slow->next;
            slow->next = p;
            p = slow;
            slow = tmp;
        }
        while (p && head)
        {
             if (p->val != head->val) return false;
             p = p->next;
             head = head->next;
        }
        return true;
    }
};

// 快慢指针+翻转链表，慢指针前进同时翻转链表
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* pre = new ListNode(-1);

        if (!head->next) return true; 
        while (fast && fast->next) {
            fast = fast->next->next;

            ListNode* tmp = slow->next;
            slow->next = pre;
            pre = slow;
            slow = tmp;
        }
        if (fast && !fast->next) 
            slow = slow->next;
        while (slow && pre) {
            if (slow->val != pre->val) return false;
            slow = slow->next;
            pre = pre->next;         
        }
        return true;
    }
};